package pro.softzhang.algo.lc900;

import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;

@KDynamicPlanning
@DRed
public class LC926_FlipStringToMonotoneIncreasing {
    public static void main(String[] args) {
        String s = "00110";
        int min = new Solution().minFlipsMonoIncr(s);
        System.out.println(min);
    }

    static class Solution {
        public int minFlipsMonoIncr(String s) {
            int[][] dp = new int[2][2];
            char c = s.charAt(0);
            dp[0][0] = c == '0' ? 0 : 1;
            dp[1][0] = c == '1' ? 0 : 1;

            for (int i = 1; i < s.length(); i++) {
                c = s.charAt(i);
                int p0 = dp[0][(i - 1) % 2];
                int p1 = dp[1][(i - 1) % 2];
                dp[0][i % 2] = p0 + (c == '0' ? 0 : 1);
                dp[1][i % 2] = Math.min(p0, p1) + (c == '1' ? 0 : 1);
            }

            return Math.min(dp[0][(s.length() - 1) % 2], dp[1][(s.length() - 1) % 2]);
        }
    }
}
